package main

import (
	"fmt"
	"sort"
)

func mergeIntervals(arr [][]int) [][]int {
	if len(arr) == 0 {
		return [][]int{}
	}

	// 步骤1：按每个区间的起始值排序
	sort.Slice(arr, func(i, j int) bool {
		return arr[i][0] < arr[j][0]
	})

	// 步骤2：合并区间
	var result [][]int
	for _, interval := range arr {
		if len(result) == 0 || result[len(result)-1][1] < interval[0] {
			// 没有重叠，直接加入
			result = append(result, interval)
		} else {
			// 有重叠，合并
			result[len(result)-1][1] = max(result[len(result)-1][1], interval[1])
		}
	}

	return result
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	arr := [][]int{{1, 3}, {2, 6}, {15, 18}}
	merged := mergeIntervals(arr)
	fmt.Println(merged) // 输出: [[1 6] [15 18]]
}
